import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Solution {
    class ListNode{
        public int val;
        public  ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    //3.输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newHead=new ListNode(-1);
        ListNode cur=newHead;
        while(l1!=null&&l2!=null){
            if(l1.val<= l2.val){
                cur.next=l1;
                l1=l1.next;
            }else{
                cur.next=l2;
                l2=l2.next;
            }
            cur=cur.next;
        }
        if(l1!=null){
            cur.next=l1;
        }
        if(l2!=null){
            cur.next=l2;
        }
        return  newHead.next;
    }
    //2.输入两个链表，找出它们的第一个公共节点。
    //第一种方法，超时
    /*
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode cur1 = headA;
        int len1 = 0;
        while (cur1 != null) {
            len1++;
            cur1 = cur1.next;
        }
        ListNode cur2 = headB;
        int len2 = 0;
        while (cur2 != null) {
            len2++;
            cur1 = cur2.next;
        }
        cur2 = headB;
        cur1 = headA;
        if (len1 >= len2) {
            int index = len1 - len2;
            while (index > 0) {
                cur1 = cur1.next;
                index--;
            }
        } else {
            int index = len2 - len1;
            while (index > 0) {
                cur2 = cur2.next;
                index--;
            }
        }
        while (cur1.val != cur2.val) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur2;
    }

     */
    //第二种方法，双指针
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return  null;
        }
        ListNode cur1=headA;
        ListNode cur2=headB;
       while(cur1!=cur2){
           cur1=cur1==null?headB:cur1.next;
           cur2=cur2==null?headA:cur2.next;
       }
       return  cur1;
    }
    //1.删除链表的倒数第 N 个结点
    //第一种方法双指针
    /*
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast=head;
        ListNode newHead=new ListNode(0,head);
        ListNode slow=newHead;
        while(n>0){
            fast=fast.next;
            n--;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return newHead.next;
    }

     */
    //第二种方法，栈
    public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode newhead=new ListNode(0);//head);//新创了一个头
            Stack<ListNode> stack=new Stack<>();
            ListNode cur=newhead;
            while(cur!=null){
                stack.push(cur);
                cur=cur.next;
            }
            while(n>0){
                stack.pop();
                n--;
            }
            ListNode node=stack.peek();
            node.next=node.next.next;
            return newhead.next;
        }
}